/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/divide-two-integers
   @Language: C++
   @Datetime: 16-02-09 05:48
   */

// Method 1, not use long
class Solution {
public:
	/**
	 * @param dividend the dividend
	 * @param divisor the divisor
	 * @return the result
	 */
	int divide(int dividend, int divisor) {
		if (divisor==0) return INT_MAX;	// overflow
		// trans to negtive number
		int a = (dividend>0 ? -dividend : dividend);
		int b = (divisor>0 ? -divisor : divisor);
		int bit = 0, ans = 0;
		for(; 0>b<<bit && bit<32; ++bit);
		while(bit--){
			if (a>b<<bit) continue;
			a -= b<<bit;
			ans += 1<<bit;
		}
		// negtive / negtive get negtive, means overflow
		if (dividend<0 && divisor<0 && ans<0) ans = INT_MAX;
		else ans = (dividend^divisor)>>31 ? -ans : ans;
		return ans;
	}
};

// Method 2, 50ms
class Solution {
	long core(long a, long b){
		if(b==1) return a;
		if(b==0) return INT_MAX;	// overflow
		if(a<0) return -core(-a,b);
		if(b<0) return -core(a,-b);
		if(a<b) return 0;
		long sum=0;
		for(long t, bit; a>=b; a-=b<<bit){
			for(t=b, bit=-1; t>0 && t<=a; t<<=1)
				++bit;
			sum+=1<<bit;
		}
		return sum;
	}
public:
	/**
	 * @param dividend: the dividend
	 * @param divisor: the divisor
	 * @return: the result
	 */
	int divide(int dividend, int divisor) {
		// write your code here
		long res = core(dividend,divisor);
		if(res>=INT_MIN && res<=INT_MAX) return res;
		else return INT_MAX;
	}
};
